Determining optimal routes is a frequent problem in many practical transportation, planning and communication applications. Of particular interest to the invention is the case where optimality is defined in terms of delay. For example, in a transportation and distribution system, there may be many possible alternative routes from a source to a destination. It is desired to deliver a packet from the source to the destination along the route that has a guaranteed minimal amount of delay.
In a planning application or manufacturing application, a task or assembly process may involve multiple alternative intermediate step from the beginning (source) to the end (destination). It is desired to complete the task or assemble a part with a guaranteed amount of delay.
In a communications application, it may be necessary to deliver a data packet from a source to a destination along a route with a minimal amount of delay. It should be noted that a minimal delay is distinguished from the more common “shortest” route problem because a shortest route, in terms of physical length, may not always be the fastest.
In the following, a wireless communications network is used as an example application. However, it is understood that the invention can be worked in many other types of routing applications as noted above.
A wireless ad-hoc network, also known as an Independent Basic Service Set (IBSS), is a network in which the communication channels between nodes, e.g., user terminals, stations, transceivers, are wireless. The network is ad hoc because its topology and routing are arbitrary, and any node can forward packets for other nodes. The determination of routes the nodes use to forward data packets is made dynamically based on network connectivity and channel state.
A wireless ad-hoc network can achieve reliable connectivity between nodes of the network. Typically, all nodes have a similar structure and functionality. The nodes are usually battery operated, and packets are forwarded from a source node to a destination node via a set of intermediate relay nodes using wireless channels connecting the nodes.
Unstructured wireless ad-hoc networks have a number of advantages over conventional structured networks, such as the Internet and cellular networks. Wireless ad-hoc networks do not require a fixed infrastructure, such as base stations, a wired backbone and routers specifically designed to route packets. This can reduce cost. Because signals can be transmitted via different alternative routes, reliability is increased. Energy consumption can decrease because intermediate relay nodes can receive and retransmit the signals via more reliable channels. Because the total transmitted energy is decreased, the lifetime of the network is increased, there is less interference, and spectral efficiency is improved. Ad hoc network are especially advantageous for battery operated transceivers.
For this reason, ad-hoc networks are frequently used for emergency response, environmental data collection, factory automation, security and military applications.
In many applications, ad-hoc networks must provide a guarantee for quality-of-service (QoS). One measure of QoS is the amount of delay incurred while transmitting the packet from the source node to the destination node. For example in an ad hoc sensor network, a packet that indicates that a piece of machinery is overheating, or otherwise malfunctioning, must be delivered to a control center before the machine ceases to function and cause more widespread damage.
The QoS in the wireless ad-hoc networks is influenced by a variety of factors including node admission, arrival statistics of packets from higher layers of a network protocol, scheduling and multiple-access mechanisms, properties of the physical layer transmission, and routing.
Due to all these variations, in particular variations in the physical layer, it is not possible to give a perfect guarantee that a packet will arrive at the destination before a deadline. It is only possible to guarantee the packets will arrive in time for a certain percentage of all channel realizations, e.g., 99%. This notion is similar in spirit to the “outage probability” of cellular networks, which defines the probability that a mobile station does not receive sufficient signal power to communicate with a base station.
Henceforth, the probability of on-time arrival is “a “probabilistic guarantee.” While stochastic variations of the delay, due to random packet arrival of the source, has been extensively described in the prior art, random variations of the transmission time due to randomly varying channels has not.
Routing is particularly important for the QoS in wireless ad-hoc networks. Routing determines the relay nodes used to forward packets from the source to the destination. Typically, routes are “discovered” and the results are stored in a routing table. A route that fulfills a particular QoS constraint, e.g., delay, is stored and maintained until the route “breaks,” i.e., the QoS constraint is violated.
Route discovery methods can generally be categorized as flooding, geometry or stateful. With flooding or “gossiping,” packets are transmitted from the source to all or randomly selected nodes. That technique does not require any knowledge of network topology or channel state information (CSI) by the nodes, but is energy inefficient because a large number of nodes are involved.
With geometry-based routing, an optimum route is determined in a central or distributed manner based on the knowledge of the location of the nodes. However, distances between nodes do not necessarily reflect propagation and delay conditions. Therefore, geometry or shortest-route based techniques can lead to suboptimum routes in terms of delay.
In stateful routing, the routing is based on the instantaneous CSI. In this category, the optimum route is determined from a global or distributed knowledge of the instantaneous CSI of all wireless channels between the nodes. For many communication applications, route discovery based on the instantaneous CSI is not practical. The state of a wireless channel can change continuously, particularly when the nodes are mobile. The typical coherence time of wireless channels is on the order of a few milliseconds. Consequently, frequent updates of the CSI throughout the network lead to an unacceptable overhead.
In large networks, the overhead of communicating the routing information for all possible nodes decreases the spectral efficiency of the network and consumes power. On-demand route discovery in large network is also not practical because the route discovery process often takes longer than the permitted delay.
Therefore, it is desired to provide a method for routing that does not have any of the above problems, and that can determine a route that has a guaranteed minimal amount of delay.